package com.leetcode.LeetCode精选TOP面试题;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-06-07 17:43
 */
public class 题库_0091_解码方法 {

  static
  class Solution {
    public int numDecodings(String s) {
      if (s == null || s.length() == 0 || s.charAt(0) == '0') {
        return 0;
      }

      int prePre = 1;
      int pre = 1;
      int cur = 1;

      for (int i = 2; i <= s.length(); ++i) {
        cur = 0;
        if (s.charAt(i - 1) != '0') {
          cur = pre;
        }
        if (s.charAt(i - 2) != '0' && (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26) {
          cur += prePre;
        }
        prePre = pre;
        pre = cur;
      }

      return cur;
    }

    private static final Set<String> coders = new HashSet<>();
    static {
      for (int i = 1; i <= 26; ++i) {
        coders.add(String.valueOf(i));
      }
    }

    public int numDecodings1(String s) {
      if (s == null || s.length() == 0) {
        return 0;
      }
      return helper(s.toCharArray(), 0);
    }

    private int helper(char[] chars, int index) {
      if (index == chars.length) {
        return 1;
      }

      int answer = 0;
      // 只取一位
      if (coders.contains("" + chars[index])) {
        answer += helper(chars, index + 1);
      }

      // 取两位
      if (index + 1 < chars.length && coders.contains("" + chars[index] + chars[index + 1])) {
        answer += helper(chars, index + 2);
      }
      return answer;
    }

  }

}
